Turbo coding of an outgoing digital data stream is one technique that may be used to mitigate the effect of RF distortion on a digital data transmission embedded within an RF signal. For example, emerging communications standards, e.g., 3rd Generation Partnership Project (3GPP) Long Term Evolution (LTE) standards, require that transceivers apply turbo coding to an outgoing data packet prior to transmission.
A rate ⅓ turbo encoder output includes three subblocks. The first subblock includes systematic bits, each systematic bit corresponding to a bit in the original data block received by the turbo encoder, the second subblock includes parity bits generated by a first recursive systematic convolutional (RSC) encoder engine within the turbo encoder that processed the original data block in a non-interleaved order, and the third subblock includes parity bits generated by a second RSC encoder engine within the turbo encoder that processed the original data block in an interleaved order.
A turbo decoder, included within a receiving device, may include two RSC decoders, each corresponding to the two RSC encoders of the turbo encoder, addressed above. The first RSC decoder may take as input the systematic bits and the parity bits produced by the first RSC encoder. The second RSC decoder may take as input the systematic bits in an interleaved order, as determined by an interleaver that uses a same turbo interleaving algorithm, π, used by, and the parity bits produced by, the second RSC encoder. In each iteration of the decoding process, each RSC decoder may output an improved estimate, e.g., extrinsic data in the form of a log-likelihood ratio (LLR), of the actual bit value represented by each systematic bit. Once the estimates generated by the two RSC decoders converge, or a predetermined number of decoding cycles have been performed, the final improved estimates may be interpreted, and transmitted from the decoder to a receiver signal processor as an output stream of decoded bit estimates.
The turbo-decoding algorithm includes multiple decoder iterations, each of which includes a non-interleaved half-iteration, followed by an interleaved half-iteration. Each half-iteration includes an alpha scan, in which the systematic bits are processed in a forward order, i.e., from first to last, and a beta scan, in which the systematic bits are processed in a reverse order, i.e., from last to first. The order in which the scans are performed depends on the implementation.
During a turbo decoding half-iteration, the beta scan and the alpha scan build and assess, respectively, a trellis logic table that is based on a series of possible logical states, e.g., binary 0 through binary 7 for rate ⅓ with constraint length 3 turbo code, that a transmitter may hold when the transmitter transmits a bit. For example, after transmitting a bit, a transmitter transitions from a state prior to the transmission, or prior-state, to one of two allowed future-states, depending on whether the systematic bit transmitted was a 0 or 1. Each allowed transition from a prior-state to a future-state represents a branch of the trellis table. For example, rate ⅓ with with constraint length 3 turbo code generates a trellis table with 8 possible transmitter states, in which each of 8 prior-states can transition to 2 of 8 possible future-states, will include 16 possible branches linking the respective 8 possible prior-states to the respective 8 possible future-states that summarize the realm of transition possibilities associated with each bit transmission. In each half-iteration of the decoding process, the alpha scan may output an improved estimate, e.g., extrinsic data in the form of a log-likelihood ratio (LLR), of the actual bit value represented by each systematic bit, based on the trellis table transmitter state metrics determined during the beta scan.
The turbo decoding process uses successive half-iteration alpha and beta scans under interleaved and non-interleaved conditions to iteratively improve the accuracy of the state transitions represented by each respective half-iteration trellis table. For example, in each turbo decoder half-iteration, the turbo decoder uses a beta scan to build a trellis table based on the systematic soft-bit metrics received from a previous turbo half-iteration, and uses the alpha scan to generate improved systematic soft-bit metrics that are further processed in the next turbo decoder half-iteration process. After several iterations, confidence in the respective trellis state transitions typically converges, i.e., a consecutive string of high confidence state transitions emerge, thereby allowing each soft-bit in the received data packet to be determined with high confidence.
The multiplexing and channel coding standard adopted as part of the 3GPP LTE standards, e.g., 3GPP Technical Specification (TS) 36.212, allows data packets that may be one of 188 different sizes, ranging between 40-bit and 6144-bit, packages. Therefore, a trellis table, built during a beta scan phase of a half-iteration, having 8 possible states per transition and that stores a 10-bit state metric for each of the 8 possible states, may require as much as 8*10*6144, or nearly 500 Kbytes, of dynamic memory to support the respective beta scan storage requirements. Implementation of sufficient memory to support such a beta scan memory requirement may represent as much as one-half the total integrated circuit footprint of a turbo decoder hardware design.